package ljl.alg.jianzhioffer.round2;

import java.util.LinkedList;

/**
 * 要求判断：对于一个二叉搜索树，当前这个序列有没有可能是它的后续遍历序列
 *
 * 我操
 * 很陌生，不会做
 *
 * 这是一道很好的好题！
 * good！
 * */
public class _33_post_order {
    
    /**
     * 递归解法，需要不停地遍历
     * 效率不是那么的高
     * */
    public boolean verifyPostorder3(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] order, int i, int j) {
        if (i >= j) return true;
        // 走一遍比 root 小的
        int s = i;
        while (order[s] < order[j]) s++;
        int m = s;
        while (order[s] > order[j]) s++;
        return s == j && recur(order, i, m - 1) && recur(order, m, j - 1);
    }
    
    /**
     * 下面这个解法就很恐怖了，不是脑子正常的人能想出来的
     *
     * 使用了单调栈：
     * 把后续遍历反过来，叫做后序遍历逆序
     *
     * 然后不知道咋的，他发现一个规律：
     * 如果是递增的，后面节点总是前面节点的右孩子，这个可以理解
     * 然后，如果发现一个递减的，那这个递减的节点，是前面某个节点的左孩子
     * 而且这个某个节点，是值最接近地递减节点的那个节点
     *      这个很不好理解了，但好像确实是这样，不知道咋推出来的
     *
     * 所以我们要构造一个递增的序列，一个比一个大
     * 这样的话，后来的节点入栈时，不停的挤走比它大的节点，同时修改 root 为被挤走的
     * 最后 root 就成比它大，同时又最小的那个节点了
     *
     * 你细品
     *
     * 每个节点都要入栈一次
     *
     * 如果发现某个节点比 root 还大，就返回 false
     *
     * 最终返回 true
     *
     * 一开始 root 初始化成正无穷
     *
     * 发现递减序列之前，不知道谁是 root，此时 root 是正无穷
     *
     * */
    public boolean verifyPostorder(int[] postorder) {
        int root = Integer.MAX_VALUE;
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = postorder.length - 1; i >= 0 ; i--) {
            if (postorder[i] > root) return false;
            while (!stack.isEmpty() && stack.peek() > postorder[i])
                root = stack.pop();
            stack.push(postorder[i]);
        }
        return true;
    }
}
